#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <map>
#include <set>

using namespace std;

// 2831. 找出最长等值子数组
// https://leetcode.cn/problems/find-the-longest-equal-subarray/description/

class Solution1
{
public:
    int longestEqualSubarray(vector<int> &nums, int k)
    {
        unordered_map<int, int> cntOfNum;
        multiset<int, greater<int>> freq;
        int maxSize = 0;
        int left = 0;
        int ans = 0;
        for (int i = 0; i < nums.size(); i++)
        {
            int curNum = nums[i];
            if (cntOfNum.find(curNum) == cntOfNum.end())
            {
                ++cntOfNum[curNum];
                freq.insert(cntOfNum[curNum]);
            }
            else
            {
                auto it = freq.find(cntOfNum[curNum]);
                freq.erase(it);
                ++cntOfNum[curNum];
                freq.insert(cntOfNum[curNum]);
            }

            maxSize = max(maxSize, cntOfNum[curNum]);

            while (i - left + 1 - maxSize > k)
            {
                int delNum = nums[left];
                auto it = freq.find(cntOfNum[delNum]);
                freq.erase(it);
                freq.insert(--cntOfNum[nums[left]]);
                left++;
                if (i - left + 1 - maxSize <= k)
                {
                    maxSize = *freq.begin();
                    break;
                }
            }
            ans = max(ans, maxSize);
        }
        return ans;
    }
};

class Solution
{
public:
    int longestEqualSubarray(vector<int> &nums, int k)
    {
        unordered_map<int, vector<int>> freq;
        for (int i = 0; i < nums.size(); i++)
        {
            freq[nums[i]].push_back(i);
        }
        int ans = 1;
        for (auto it : freq)
        {
            vector<int> &curNum = it.second;
            int left = curNum[0];
            int preIndex = 0;
            for (int i = 1; i < curNum.size(); i++)
            {
                int curIndex = curNum[i];
                while(curIndex - left + 1 - (i - preIndex + 1) > k){
                    left = curNum[++preIndex];
                }
                ans = max(ans, i - preIndex + 1);
            }
        }
        return ans;
    }
};

int main()
{
    vector<int> nums{1, 1, 2, 2, 6, 2};
    int k = 1;
    Solution solution{};
    solution.longestEqualSubarray(nums, k);
    return 0;
}